home *** CD-ROM | disk | FTP | other *** search
/ Turnbull China Bikeride / Turnbull China Bikeride - Disc 2.iso / STUTTGART / EMULATOR / GBDK_BIN / examples / c / sort < prev    next >
Text File  |  1996-04-15  |  1KB  |  79 lines
  1. #include<stdio.h>
  2.  
  3. int in[10];
  4.  
  5. main() {
  6.     int i;
  7.  
  8.     in[0] = 10;
  9.     in[1] = 32;
  10.     in[2] = -1;
  11.     in[3] = 567;
  12.     in[4] = 3;
  13.     in[5] = 18;
  14.     in[6] = 1;
  15.     in[7] = -51;
  16.     in[8] = 789;
  17.     in[9] = 0;
  18.  
  19.     sort(in, (sizeof in)/(sizeof in[0]));
  20.     for (i = 0; i < (sizeof in)/(sizeof in[0]); i++) {
  21.         putd(in[i]);
  22.         putchar('\n');
  23.     }
  24.     return 0;
  25. }
  26.  
  27. /* putd - output decimal number */
  28. putd(n) {
  29.     if (n < 0) {
  30.         putchar('-');
  31.         n = -n;
  32.     }
  33.     if (n/10)
  34.         putd(n/10);
  35.     putchar(n%10 + '0');
  36. }
  37.  
  38. int *xx;
  39.  
  40. /* sort - sort a[0..n-1] into increasing order */
  41. sort(a, n) int a[]; {
  42.     quick(xx = a, 0, --n);
  43. }
  44.  
  45. /* quick - quicksort a[lb..ub] */
  46. quick(a, lb, ub) int a[]; {
  47.     int k, partition();
  48.  
  49.     if (lb >= ub)
  50.         return;
  51.     k = partition(a, lb, ub);
  52.     quick(a, lb, k - 1);
  53.     quick(a, k + 1, ub);
  54. }
  55.  
  56. /* partition - partition a[i..j] */
  57. int partition(a, i, j) int a[]; {
  58.     int v, k;
  59.  
  60.     j++;
  61.     k = i;
  62.     v = a[k];
  63.     while (i < j) {
  64.         i++; while (a[i] < v) i++;
  65.         j--; while (a[j] > v) j--;
  66.         if (i < j) exchange(&a[i], &a[j]);
  67.     }
  68.     exchange(&a[k], &a[j]);
  69.     return j;
  70. }
  71.  
  72. /* exchange - exchange *x and *y */
  73. exchange(x, y) int *x, *y; {
  74.     int t;
  75.  
  76.     printf("exchange(%d,%d)\n", x - xx, y - xx);
  77.     t = *x; *x = *y; *y = t;
  78. }
  79.